#include <iostream>

using namespace std;

const int N = 1e5 + 10;

// 创建双链表
int e[N], ne[N], pre[N], id, h;
int mp[N]; // mp[i] 表示：i 这个值存储的位置

class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return;  // 空链表或单节点无需处理
        
        // 1. 找链表中点（前半段尾节点）
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 2. 逆序后半段
        ListNode* prev = nullptr;
        ListNode* curr = slow->next;  // 后半段头节点
        slow->next = nullptr;         // 切断前半段与后半段
        while (curr != nullptr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        ListNode* p2 = prev;  // 逆序后半段的头节点
        
        // 3. 合并前半段（p1）和逆序后半段（p2）
        ListNode* p1 = head;
        while (p1 != nullptr && p2 != nullptr) {
            ListNode* p1Next = p1->next;
            ListNode* p2Next = p2->next;
            
            p1->next = p2;       // p1 后接 p2
            p2->next = p1Next;   // p2 后接 p1 的下一个节点
            
            p1 = p1Next;         // 移动 p1
            p2 = p2Next;         // 移动 p2
        }
    }
};